package com.tree;

public class RBT<E extends Comparable<E>>  {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node{
        private E e;
        private Node left;
        private Node right;
        private boolean color;

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
            this.color = RED;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    ", left=" + left +
                    ", right=" + right +
                    ", color='" + color + '\'' +
                    '}';
        }
    }
    private Node root;
    private int size;
    private int height;
    public void add(E e){
        root = add(root,e);
        root.color = BLACK;
    }

    /**
     * 在以root为根的树中，插入e
     * @param root
     * @param e
     * @return 返回插入结点（新的子树的根节点）
     */
    private Node add(Node root, E e) {
        if (root == null){
            size++;
            return new Node(e);
        }

        if (e.compareTo(root.e)<0){
            root.left = add(root.left,e);
        } else if (e.compareTo(root.e)>0){
            root.right = add(root.right, e);
        }
        //左旋
        if (isRed(root.right)&&!isRed(root.left)){
            root = leftRotate(root);
        }
        //先左子树左旋，然后右旋
        if(isRed(root.left)&&isRed(root.left.right)){
            root.left = leftRotate(root.left);
            root = rightRotate(root);
        }
        //右旋
        if(isRed(root.left)&&isRed(root.left.left)){
            root = rightRotate(root);
        }
        //颜色翻转
        if (isRed(root.left)&&isRed(root.right)){
            flipColors(root);
        }

        return root;
    }

    private Node rightRotate(Node root) {
        if (root == null)
            return null;
        Node x = root.left;

        root.left = x.right;
        x.right = root;

        x.color = root.color;
        root.color = RED;

        return x;
    }

    private void flipColors(Node root) {
        root.color = RED;
        root.left.color = BLACK;
        root.right.color = BLACK;
    }

    private Node leftRotate(Node root) {
        if (root == null)
            return null;
        Node x = root.right;
        Node y = x.left;

        x.left = root;
        root.right = y;

//        x.color = BLACK;
        x.color = root.color;
        root.color = RED;

        return x;

    }

    private boolean isRed(Node right) {
        if (right == null)
            return BLACK;
        return right.color;
    }
}
